[UOJ310]-黎明前的巧克力

求的就是 $\sum\limits_{xor(S) = 0} 2^{|S|}$

考虑它的生成函数: $\prod (1 + 2x^{\{a_i\}})$，其中这里的 $\prod$ 表示异或卷积

直接 FWT + 点乘 肯定不行。。

发现对 $(1 + 2x^{a_i})$ 做 FWT 后的点值不是 -1 就是 3（1 也就是 $x^0$，它对每位的贡献是 1，$2x^{a_i}$ 对每位的贡献是 2 或 -2），那么我们只要知道每位有多少个 -1/3 就好了

有个性质：线性变换的和 = 和的线性变换，于是我们把所有多项式加起来做一遍 FWT，对于第 $i$ 位设有 $k$ 个 -1，那么 $-k + 3(n - k) = f_i$（$f_i$ 就是和的 FWT），就能解出 $k$，也就得到了第 $i$ 位点乘的结果！然后一遍 IFWT 就好了！！

#include <bits/stdc++.h>
#define rep(i, x, y) for (int i = x; i <= y; i++)
using namespace std;

typedef long long ll;
const int mod = 998244353, N = 2e6 + 10, inv2 = (mod + 1) / 2;
ll n, a[N], f[N], bit3[N];

ll quick_pow(ll a, ll b) {
    ll ret = 1;
    for (; b; b >>= 1) {
        if (b & 1) ret = ret * a % mod;
        a = a * a % mod;
    } return ret;
}

void FWT_xor(ll a[], int n, int op) {
    rep(i, 1, n)
        rep(j, 0, (1 << n) - 1)
            if (!((j >> (i - 1)) & 1)) {
                ll x = a[j], y = a[j + (1 << (i - 1))];
                a[j] = (x + y) % mod, a[j + (1 << (i - 1))] = (x - y + mod) % mod;
                if (op == -1) (a[j] *= inv2) %= mod, (a[j + (1 << (i - 1))] *= inv2) %= mod;
            }
}

int main() {
    cin >> n;
    f[0] = n;
    bit3[0] = 1;
    rep(i, 1, n) {
        scanf("%lld", &a[i]);
        bit3[i] = bit3[i - 1] * 3 % mod;
        f[a[i]] += 2;
    }
    FWT_xor(f, 20, 1);
    ll inv4 = quick_pow(4, mod - 2);
    rep(i, 0, (1 << 20) - 1) {
        int k = ((3 * n - f[i] + mod) % mod) * inv4 % mod;
        f[i] = (k & 1 ? mod - bit3[n - k] : bit3[n - k]);
    }
    FWT_xor(f, 20, -1);
    printf("%lld\n", (f[0] - 1 + mod) % mod);  // 减去空集
    return 0;
}